package me.huangxiang.data_structure_and_algorithm.algorithms.recursion;

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    // 简单递归
    public static int fibonacci(int n){
        if (n < 2){
            return n;
        }else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }


    // 使用备忘录法
    private static Map<Integer, Long> cache = new HashMap<>();
    public static long fibonacciUsingCache(int n){
        if (n < 2){
            return n;
        } else {
            if (cache.containsKey(n)){
                return cache.get(n);
            }else {
                long value = fibonacciUsingCache(n - 1) + fibonacciUsingCache(n - 2);
                cache.put(n, value);
                return value;
            }
        }
    }


    // 使用迭代的方式
    public static long fibonacciUsingDynamicProgramming(int n){
        if (n < 2){
            return n;
        } else {
            int a = 1;
            int b = 1;
            int tmp = 0;

            for (int i = 3; i <= n; i++){
                tmp = a + b;
                a = b;
                b = tmp;
            }
            return tmp;
        }
    }
}
